//二叉树用二叉链表结构存储，统计二叉树中度为1的结点个数，输出所有叶子结点
#include<stdio.h>
#include<stdlib.h>

typedef struct Node
{
    int data;
    struct Node *lchild,*rchild;
}Node;

int countAll(Node* root,int* count);
int countZero(Node* root,int* count);
int printAllZeroAndCountOne(Node* root,int* count);
int printAllZero(Node* root);




int main(){
    Node root;
    root.data=1;
    root.lchild = (Node*)malloc(sizeof(Node));
    root.lchild->data=2;root.lchild->lchild=(Node*)malloc(sizeof(Node));
    root.lchild->lchild->data=4;
    root.rchild = (Node*)malloc(sizeof(Node));
    root.rchild->data=3;
    root.rchild->lchild=(Node*)malloc(sizeof(Node));root.rchild->rchild=(Node*)malloc(sizeof(Node));
    root.rchild->lchild->data=5;root.rchild->rchild->data=6;

    int all=0,one=0,two=0,zero=0;
    countAll(&root,&all);
    countZero(&root,&zero);
    two=zero-1;
    one=all-zero-two;
    printf("结点总个数为%d,度为0的结点的个数%d,度为1的结点的个数%d,度为2的结点的个数%d",all,zero,one,two);
}

int countAll(Node* root,int* count){
    if(root==NULL){
        return 0;
    }
    *count=(*count)+1;
    countAll(root->lchild,count);
    countAll(root->rchild,count);
    return 0;
}

int countZero(Node* root,int* count){
    if(root==NULL){
        return 0;
    }
    if(root->lchild==NULL && root->rchild==NULL){
        *count=(*count)+1;
    }
    countZero(root->lchild,count);
    countZero(root->rchild,count);
    return 0;
}

int printAllZero(Node* root){
    if(root==NULL){
        return 0;
    }
    if(root->lchild==NULL && root->rchild==NULL){
        printf("%d ",root->data);
    }
    printAllZero(root->lchild);
    printAllZero(root->rchild);
    return 0;
}


int printAllZeroAndCountOne(Node* root,int* count){
    if(root==NULL){
        return 0;
    }
    if(root->lchild==NULL && root->rchild==NULL){
        printf("%d ",root->data);
    }
    int du=0;
    if(root->lchild!=NULL){
        du+=1;
    } 
    if(root->rchild!=NULL){
        du+=1;
    }
    if(du==1){
        *count=(*count)+1;
    }
    printAllZeroAndCountOne(root->lchild,count);
    printAllZeroAndCountOne(root->rchild,count);

    return 0;
}


